package algorithms.sorts;

import algorithms.Utils;
import algorithms.sorts.radix.RadixSequenceAdapter;
import algorithms.sorts.radix.RadixKey;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class RadixSort {


    public static void main(String[] args) {
        Integer[] arr = Utils.randomBoxedArray(10000000, -10000, 10000);
        RadixSequenceAdapter<Integer> context = RadixSequenceAdapter.wrapIntArray(arr);

        long start = System.currentTimeMillis();
        System.out.println("radixSort start:" + System.currentTimeMillis());
        radixSort(context);
        long end = System.currentTimeMillis();
        System.out.println("  radixSort end:" + end);
        System.out.println("  radixSort use:" + (end - start));

        System.out.println(Arrays.toString(arr));
        System.out.println(Utils.isAscend(arr));

    }

    @SuppressWarnings("unchecked")
    private static <T extends Comparable<T>> void radixSort(RadixSequenceAdapter<T> adapter) {
        int radixCount = adapter.maxRadixCount();
        List<RadixKey<T>>[] buckets = null;
        for (int i = 1; i <= radixCount; i++) {
            int count = adapter.keyCountAt(i);

            if (buckets == null || count <= buckets.length /*不大于上次桶容量则复用*/) {
                buckets = new ArrayList[count];
            }

            for (int j = 0; j < adapter.size(); j++) {
                RadixKey<T> e = adapter.getKey(j);
                int position = e.positionAt(i);
                List<RadixKey<T>> bucket = buckets[position];
                if (bucket == null) {
                    buckets[position] = bucket = new ArrayList<>();
                }
                bucket.add(e);
            }
            int k = 0;
            for (int j = 0; j < count; j++) {
                List<RadixKey<T>> bucket = buckets[j];
                if (bucket != null) {
                    for (RadixKey<T> v : bucket) {
                        adapter.set(k++, v.value());
                    }
                    //清空，并置为null
                    bucket.clear();
                    buckets[j] = null;
                }
            }
        }

    }

}
